#include <stdio.h>
#include <stdlib.h>

int *poz;		// Pozicije kraljica po jednoj osi
int *pok;		// Broj pokusaja u pojedinom koraku
int tabla;		// Velicina table

/* Provera da li se dve kraljice na pozicijama (x1, y1) i (x2, y2) napadaju */
inline int napad(int x1, int y1, int x2, int y2)
{
	if(x1 == x2) return 1;
	if(y1 == y2) return 1;
	if(x1 + (y2 - y1) == x2) return 1;
	if(x1 - (y2 - y1) == x2) return 1;
	if(y1 + (x2 - x1) == y2) return 1;
	if(y1 - (x2 - x1) == y2) return 1;
	return 0;
}

/* Pomeranje kraljice na sledecu mogucu poziciju (inkrement po modulu velicine table) */
inline void inc(int k) { poz[k] = (poz[k] + 1) % tabla; }

/* Trazenje moguce pozicije za kraljicu k, tako sto ce se njena pozicija testirati sa
 * pozicijama svih kraljica pre nje. Ako je pronadjena, kraljica ce biti postavljena
 * na tu poziciju i funkcija ce vratiti 1, ako ne, na originalnu i 0 ce biti vracena. */
int pronadjiDobruPoziciju(int k)
{
	int i, j, ok;
	for(i = 0; i < tabla - 1; i++)
	{
		ok = 1;
		for(j = 0; j < k; j++)
		{
			if(napad(k, poz[k], j, poz[j]))
			{
				ok = 0;
				break;
			}
		}

		if(ok)
		{
			return 1;
		}

		inc(k);
	}
	inc(k);
	return 0;
}

/* Trazenje resenja za n kraljica, odnosno n x n tablu. Ako je u trenutnoj iteraciji
 * pronadjena dobra pozicija za trenutnu kraljicu, prelazi se na sledeci nivo, tj.
 * sledecu kraljicu. Ako se pozicija ne moze naci, ili je vec isprobano ukupno 8
 * pozicija, vracamo se na prethodni nivo. Kraj nastaje kada je i poslednja kraljica
 * uspesno smestena na tablu. */
void pronadjiResenje(int n)
{
	int nivo = 1;
	tabla = n;

	poz = (int*)calloc(tabla, sizeof(int));
	pok = (int*)calloc(tabla, sizeof(int));

	do
	{
		if(pok[nivo] >= tabla || !pronadjiDobruPoziciju(nivo))
		{
			nivo--;
			inc(nivo);
			pok[nivo]++;
		}
		else
		{
			nivo++;
			pok[nivo] = 0;
		}

	} while(nivo < tabla);
}

/* Primer trazenja resenja za n = 15 i ispis pronadjenih pozicija. */
int main(void) {

	int i;
	pronadjiResenje(15);
	for(i = 0; i < tabla; i++)
		printf("%d ", poz[i]);
	printf("\n");

	return EXIT_SUCCESS;
}
